package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202410;

import java.util.Arrays;

public class leetcode20241003 {
    public int minCost(int maxTime,int[][] edges,int[] passingFees){
        /**
         * 规定时间内到达终点的最小花费：动态规划算法，从0到n-1的最小花费
         */
        int n=passingFees.length;
        int[][] f=new int[maxTime+1][n];// 在时间maxTime内到达城市n
        for(int i=0;i<=maxTime;i++){
            Arrays.fill(f[i],Integer.MAX_VALUE);
        }
        f[0][0]=passingFees[0];
        for(int t=1;t<=maxTime;t++){
            for(int[] edge : edges){
                int i=edge[0],j=edge[1],cost=edge[2];
                if(cost<=t){
                    if(f[t-cost][j]!=Integer.MAX_VALUE){// j->i
                        f[t][i]=Math.min(f[t][i],f[t-cost][j]+passingFees[i]);
                    }

                    if(f[t-cost][i]!=Integer.MAX_VALUE){// i->j
                        f[t][j]=Math.min(f[t][j],f[t-cost][i]+passingFees[j]);
                    }
                }
            }
        }
        int ans=Integer.MAX_VALUE;
        for(int t=1;t<=maxTime;t++){
            ans=Math.min(ans,f[t][n-1]);
        }
        return ans;
    }
}
